package summary;

/**
 * @Author: 海琳琦
 * @Date: 2022/3/13 15:13
 * https://leetcode-cn.com/problems/maximum-length-of-repeated-subarray/
 */
public class Title718 {

    /**
     * dp[i][j]表示：以下标i-1结尾的A，以下标j-1结尾的B，最长重复长度为dp[i][j]
     * 递推公式：
     * 如果nums1[i-1] == nums2[j-1]  ------>  dp[i][j] = dp[i - 1][j - 1] + 1
     * @param nums1
     * @param nums2
     * @return
     */
    public static int findLength(int[] nums1, int[] nums2) {
        int max = 0;
        int[][] dp = new int[nums1.length + 1][nums2.length + 1];
        for (int i = 1; i <= nums1.length; i++) {
            for (int j = 1; j <= nums2.length; j++) {
                if (nums1[i - 1] == nums2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    if (dp[i][j] > max) {
                        max = dp[i][j];
                    }
                }
            }
        }
        return max;
    }


    public static int findLength3(int[] nums1, int[] nums2) {
        int n = nums1.length;
        int m = nums2.length;
        //dp[i][j]表示下标为i-1, j-1时的两数组最长的公共子数组长度
        //nums1[i] = nums2[j]   dp[i][j] = dp[i-1][j-1]+1
        //nums1[i] != num2[j]   dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1])
        int max = 0;
        int[][] dp = new int[n + 1][m + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (nums1[i - 1] == nums2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    if (dp[i][j] > max) {
                        max = dp[i][j];
                    }
                }
            }
        }
        return max;
    }


    public static void main(String[] args) {
        int[] nums1 = {0,1,1,1,1};
        int[] nums2 = {1,0,1,0,1};
        int length = findLength3(nums1, nums2);
        System.out.println(length);
    }
}
